package Midium;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

// 数组中的第k个最大元素
public class Solution215 {
    public static void main(String[] args) {
        findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4);
    }

    /*
     * 思路:遍历一遍，保存在treeMap里
     * 遍历一遍treeMap,找到第k个最大的数
     * */
    public static int findKthLargest(int[] nums, int k) {
        Map<Integer, Integer> treeMap = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1; //比的是key 从大到小排序
            }
        });
        for (int i = 0; i < nums.length; i++) {
            if (treeMap.containsKey(nums[i])) {
                treeMap.replace(nums[i], treeMap.get(nums[i]) + 1);
            } else {
                treeMap.put(nums[i], 1);
            }
        }
        int t = 0;
        for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
            t += entry.getValue();
            if (t >= k) {
                return entry.getKey();
            }
        }
        return -1;
    }
}
